﻿#define _CRT_SECURE_NO_WAENINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

//将数组排序之后，比较每对相邻的元素，即可找到错误的集合。
//
//寻找重复的数字较为简单，如果相邻的两个元素相等，则该元素为重复的数字。
//
//寻找丢失的数字相对复杂，可能有以下两种情况：
//
//如果丢失的数字大于 1 且小于 n，则一定存在相邻的两个元素的差等于 2，这两个元素之间的值即为丢失的数字；
//
//如果丢失的数字是 1 或 n，则需要另外判断。
//
//为了寻找丢失的数字，需要在遍历已排序数组的同时记录上一个元素，然后计算当前元素与上
// 一个元素的差。考虑到丢失的数字可能是 1，因此需要将上一个元素初始化为 0
//
//当丢失的数字小于 n 时，通过计算当前元素与上一个元素的差，即可得到丢失的数字；
//
//如果 nums[n−1]≠n，则丢失的数字是 n
void InsertSort(int* a, int n)
{

	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}

			else
			{
				break;
			}

		}
		a[end + 1] = tmp;
	}
}

int* findErrorNums(int* nums, int numsSize, int* returnSize)
{
	int* errorNums = (int*)malloc(sizeof(int) * 2);
	*returnSize = 2;
	InsertSort(nums, numsSize);//对数组进行排序
	int prev = 0;//记录前一个元素的值
	for (int i = 0; i < numsSize; i++)
	{
		int curr = nums[i];//记录当前元素值
		if (curr == prev) //判断重复的数据
		{
			errorNums[0] = prev;
		}
		else if (curr - prev > 1) //curr减去prev
		{
			errorNums[1] = prev + 1;
		}
		prev = curr;//更新prev值
	}
	if (nums[numsSize - 1] != numsSize) //判断是否是n值被替换
	{
		errorNums[1] = numsSize;
	}
	return errorNums;
}

int main()
{
	int a[] = { 3,2,3,4,6,5 };
	int len = sizeof(a) / sizeof(a[0]);
	int returnsize = 0;
	int* b = (int*)malloc(sizeof(int) * 2);
	b=findErrorNums(a, len, &returnsize);
	for (int i = 0; i < 2; i++)
	{
		printf("%d ", b[i]);
	}
	return 0;
}